#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
自适应签名驱动虚拟段调度算法
================================================

本算法实现了一个智能的高带宽内存(HBM)调度系统，用于计算任务中的内存管理。
它采用基于虚拟段的方法，结合自适应策略进行内存分配、驱逐和预取。

核心特性：
    - 虚拟段合并以降低 I/O 开销
    - 基于前瞻的自适应预取
    - 使用距离评分的智能驱逐选择
    - 基于工作负载特征的动态策略选择
"""

import sys
import math
import gc

# ==========================================
# 配置常量 (Configuration Constants)
# ==========================================

# 提升递归深度限制，用于复杂调度场景中的深层调用栈
sys.setrecursionlimit(50000)

# 哨兵值，表示无限时间（用于不再被访问的段）
INFINITY_USE = 10**18


# ==========================================
# 核心组件 (Core Components)
# ==========================================

class OutputBuffer:
    """
    内存操作的输出缓冲区
    
    管理内存操作（Reload、Offload、Visit）的缓冲和格式化。
    实现策略性的操作合并以降低 I/O 开销，同时保持正确性。
    
    关键设计决策: 仅合并 Reload 操作；Offload 操作保持独立以防止内存一致性问题。
    
    属性:
        buffer (list): 操作元组列表 (time, op_type, physical_addr, size)
    """
    
    def __init__(self):
        """初始化空的输出缓冲区"""
        self.buffer = []
    
    def append(self, time, op_type, physical_addr, size):
        """
        添加内存操作到缓冲区并智能合并
        
        参数:
            time (int): 操作开始时间戳
            op_type (str): 操作类型 - "Reload"、"Offload" 或 "Visit"
            physical_addr (int): 物理内存起始地址
            size (int): 操作大小（字节），Visit 操作为 0
        
        注意:
            - size=0 的 Visit 操作总是被添加
            - Reload 操作在时间和地址连续时会被合并
            - Offload 操作永不合并以保持内存安全性
        """
        # 跳过大小为 0 的非 Visit 操作
        if size == 0 and op_type != "Visit":
            return
        
        # 尝试与最后一个操作合并
        if self.buffer:
            last = self.buffer[-1]
            if last[1] == op_type:
                # 关键：只合并 Reload 操作
                if op_type == "Reload":
                    last_end_time = last[0] + 40 * last[3]  # 每字节 40 周期
                    last_end_addr = last[2] + last[3]
                    
                    # 在时间和地址空间都连续时合并
                    if last_end_time == time and last_end_addr == physical_addr:
                        self.buffer[-1] = (last[0], last[1], last[2], last[3] + size)
                        return
        
        # 无法合并时添加新操作
        self.buffer.append((time, op_type, physical_addr, size))
    
    def flush(self):
        """
        按时间戳排序操作并格式化为输出
        
        返回:
            list[str]: 格式化的操作字符串列表
        
        注意:
            操作按时间戳排序以确保时间顺序。
            Visit 操作格式化时不包含 size 参数。
        """
        self.buffer.sort(key=lambda x: x[0])
        res = []
        for t, op, addr, size in self.buffer:
            if op == "Visit":
                res.append(f"{op} {t} {addr}")
            else:
                res.append(f"{op} {t} {addr} {size}")
        return res


class UniversalPlanner:
    """
    通用内存规划引擎 - 自适应策略
    
    核心调度算法，管理多个任务组的内存操作。
    支持针对不同工作负载模式的可配置策略。
    
    **核心概念**:
        - 虚拟段(Virtual Segments): 通过合并具有相同访问模式的物理段创建的逻辑内存单元
        - 签名(Signatures): 定义哪些任务组访问每个段的时间访问模式
        - 前瞻(Lookahead): 预取时考虑的未来任务组数量
    
    **策略**:
        - enable_merge=True: 合并具有相同签名的段（更快的 I/O）
        - enable_merge=False: 保持段独立（精确的内存控制）
        - lookahead: 控制预取激进程度（50-200 个任务组）
    
    属性:
        input_data (list): 来自 stdin 的原始输入数据
        ENABLE_MERGE (bool): 是否合并具有相同签名的虚拟段
        LOOKAHEAD_DEPTH (int): 预取的未来任务组数量
    """
    
    def __init__(self, input_data, enable_merge=True, lookahead=100):
        """
        使用指定策略初始化通用规划器
        
        参数:
            input_data (list): 来自 stdin 的分词输入数据
            enable_merge (bool): 启用虚拟段合并（默认: True）
            lookahead (int): 预取前瞻深度（默认: 100 个任务组）
        """
        self.input_data = input_data
        self.ENABLE_MERGE = enable_merge
        self.LOOKAHEAD_DEPTH = lookahead
    
    def run(self):
        """
        执行主调度算法
        
        此方法协调整个调度过程：
        1. 解析输入并离散化地址空间
        2. 构建任务组并计算访问签名
        3. 基于合并策略创建虚拟段
        4. 执行主调度循环，包括驱逐和预取
        5. 输出格式化的操作
        
        算法使用多阶段方法平衡 I/O 效率和内存利用率。
        """
        # 在调度期间禁用垃圾回收以提升性能
        gc.disable()
        
        if not self.input_data:
            print("Fin 0")
            return
        
        # ==========================================
        # 阶段 1: 输入解析 (Input Parsing)
        # ==========================================
        iterator = iter(self.input_data)
        try:
            self.L = int(next(iterator))  # 总地址空间大小
            self.M = int(next(iterator))  # HBM 容量
            self.N = int(next(iterator))  # 请求数量
            
            # 解析所有请求: (地址, 大小, 开始时间, 持续时间, 请求ID)
            self.requests_raw = []
            for i in range(self.N):
                self.requests_raw.append((
                    int(next(iterator)),  # 地址
                    int(next(iterator)),  # 大小
                    int(next(iterator)),  # 开始时间
                    int(next(iterator)),  # 持续时间
                    i                     # 请求 ID
                ))
        except StopIteration:
            return
        
        if self.N == 0:
            print("Fin 0")
            return
        
        # ==========================================
        # 阶段 2: 地址空间离散化 (Address Space Discretization)
        # ==========================================
        # 在所有请求边界创建段以避免部分重叠
        points = {0, self.L}
        for r in self.requests_raw:
            points.add(r[0])              # 起始地址
            points.add(r[0] + r[1])       # 结束地址
        sorted_points = sorted(list(points))
        
        # 构建临时物理段
        temp_starts = []
        temp_sizes = []
        addr_to_temp_idx = {}
        curr_idx = 0
        
        for i in range(len(sorted_points) - 1):
            start = sorted_points[i]
            size = sorted_points[i+1] - start
            if size > 0:
                temp_starts.append(start)
                temp_sizes.append(size)
                addr_to_temp_idx[start] = curr_idx
                curr_idx += 1
        
        temp_num_segs = len(temp_starts)
        
        # ==========================================
        # 阶段 3: 任务分组与签名生成 (Task Grouping and Signature Generation)
        # ==========================================
        # 按开始时间分组请求
        groups_map = {}
        for i, r in enumerate(self.requests_raw):
            s_time = r[2]
            if s_time not in groups_map:
                groups_map[s_time] = []
            groups_map[s_time].append(i)
        
        sorted_start_times = sorted(groups_map.keys())
        num_groups = len(sorted_start_times)
        
        # 计算每个物理段的访问签名
        # 签名 = 访问该段的任务组索引元组
        temp_signatures = [[] for _ in range(temp_num_segs)]
        raw_group_infos = []
        
        for g_idx, s_time in enumerate(sorted_start_times):
            req_indices = groups_map[s_time]
            duration = self.requests_raw[req_indices[0]][3]
            raw_group_infos.append((s_time, duration, req_indices))
            
            # 标记该任务组访问的段
            for r_idx in req_indices:
                r = self.requests_raw[r_idx]
                start_idx = addr_to_temp_idx[r[0]]
                r_size = r[1]
                acc = 0
                curr = start_idx
                
                # 遍历该请求覆盖的所有段
                while acc < r_size:
                    if not temp_signatures[curr] or temp_signatures[curr][-1] != g_idx:
                        temp_signatures[curr].append(g_idx)
                    acc += temp_sizes[curr]
                    curr += 1
        
        # 将签名转换为元组以便哈希
        temp_signatures = [tuple(s) for s in temp_signatures]
        
        # ==========================================
        # 阶段 4: 虚拟段创建 (Virtual Segment Creation)
        # ==========================================
        # 策略: 合并具有相同签名的段（如果启用）
        sig_to_vid = {}
        self.v_seg_total_size = []
        self.v_seg_access_groups = []
        self.v_seg_sub_segments = []
        curr_vid = 0
        
        for i in range(temp_num_segs):
            sig = temp_signatures[i]
            if not sig:
                continue
            
            # 核心策略分支: 按签名合并或保持独立
            key = sig if self.ENABLE_MERGE else (i,)
            
            if key not in sig_to_vid:
                sig_to_vid[key] = curr_vid
                self.v_seg_total_size.append(0)
                self.v_seg_access_groups.append(sig)
                self.v_seg_sub_segments.append([])
                curr_vid += 1
            
            vid = sig_to_vid[key]
            p_start = temp_starts[i]
            p_size = temp_sizes[i]
            self.v_seg_total_size[vid] += p_size
            
            # 合并同一虚拟段内的连续物理段
            subs = self.v_seg_sub_segments[vid]
            if subs and subs[-1][0] + subs[-1][1] == p_start:
                # 扩展最后一个子段
                subs[-1] = (subs[-1][0], subs[-1][1] + p_size)
            else:
                # 添加新子段
                subs.append((p_start, p_size))
        
        num_v_segs = curr_vid
        
        # 预计算大小的平方根倒数用于评分
        # 用于驱逐选择: 较小的段具有更高的驱逐优先级
        self.inv_sqrt_sizes = [1.0 / (math.sqrt(s) + 1e-5) for s in self.v_seg_total_size]
        
        # ==========================================
        # 阶段 5: 构建辅助数据结构 (Build Auxiliary Data Structures)
        # ==========================================
        # 将每个任务组映射到其需要的虚拟段
        self.group_needed_vsegs = [[] for _ in range(num_groups)]
        group_data_demand = [0] * num_groups
        
        for vid, g_list in enumerate(self.v_seg_access_groups):
            sz = self.v_seg_total_size[vid]
            for g_idx in g_list:
                self.group_needed_vsegs[g_idx].append(vid)
                group_data_demand[g_idx] += sz
        
        # 构建任务组元数据: (开始时间, 持续时间, 请求IDs)
        self.group_info = []
        for s_time, dur, r_indices in raw_group_infos:
            self.group_info.append((s_time, dur, [self.requests_raw[x][4] for x in r_indices]))
        
        # 计算每个任务组的 I/O 密度因子
        # 更高的密度 = 更需要带宽的工作负载
        group_density_factor = [1.0] * num_groups
        avg_bw = 0.025  # 基线带宽（1/40）
        
        for i in range(num_groups):
            dur = self.group_info[i][1]
            demand = group_data_demand[i]
            bw = demand / dur if dur > 0 else demand
            group_density_factor[i] = max(1.0, bw / avg_bw)
        
        # ==========================================
        # 阶段 6: 初始化运行时状态 (Initialize Runtime State)
        # ==========================================
        # 跟踪每个虚拟段的已加载范围（区间集）
        v_seg_loaded_ranges = [[] for _ in range(num_v_segs)]
        
        # 跟踪每个段变得可访问的时间（NPU 完成后）
        v_seg_unlock_time = [0] * num_v_segs
        
        # 下次访问查找的缓存（优化以避免重复扫描）
        v_seg_next_access_ptr = [0] * num_v_segs
        
        # 当前已加载的虚拟段 ID 集合
        loaded_v_seg_indices = set()
        
        # 当前 HBM 使用量（字节）
        current_hbm_usage = 0
        
        # 操作的输出缓冲区
        out_buf = OutputBuffer()
        
        # 全局 I/O 时间线（当前 I/O 完成时间）
        T_io = 0
        
        # 最后一次 NPU 完成时间（用于依赖跟踪）
        last_group_compute_end = 0
        
        # 所有任务组的预估开始时间（用于预取）
        est_group_start_time = [0] * num_groups
        curr_est = 0
        for i in range(num_groups):
            curr_est = max(curr_est, self.group_info[i][0])
            est_group_start_time[i] = curr_est
            curr_est += self.group_info[i][1]
        
        # ==========================================
        # 辅助函数
        # ==========================================
        
        def get_loaded_amount(vid):
            """
            计算虚拟段的已加载总字节数
            
            参数:
                vid (int): 虚拟段 ID
            
            返回:
                int: 当前 HBM 中已加载的总字节数
            """
            return sum(end - start for start, end in v_seg_loaded_ranges[vid])
        
        def merge_intervals(intervals):
            """
            合并重叠或相邻的区间
            
            参数:
                intervals (list): (start, end) 元组列表
            
            返回:
                list: 按起始位置排序的合并区间
            """
            if not intervals:
                return []
            intervals.sort()
            merged = [intervals[0]]
            for start, end in intervals[1:]:
                if start <= merged[-1][1]:
                    # 重叠或相邻: 合并
                    merged[-1] = (merged[-1][0], max(merged[-1][1], end))
                else:
                    # 不相交: 添加新区间
                    merged.append((start, end))
            return merged
        
        def add_loaded_range(vid, start, end):
            """
            将逻辑范围标记为已加载
            
            参数:
                vid (int): 虚拟段 ID
                start (int): 逻辑起始偏移量
                end (int): 逻辑结束偏移量（不包含）
            """
            if start >= end:
                return
            v_seg_loaded_ranges[vid].append((start, end))
            v_seg_loaded_ranges[vid] = merge_intervals(v_seg_loaded_ranges[vid])
            if v_seg_loaded_ranges[vid]:
                loaded_v_seg_indices.add(vid)
        
        def remove_loaded_range(vid, start, end):
            """
            将逻辑范围标记为已卸载
            
            参数:
                vid (int): 虚拟段 ID
                start (int): 逻辑起始偏移量
                end (int): 逻辑结束偏移量（不包含）
            """
            if start >= end:
                return
            new_ranges = []
            for r_start, r_end in v_seg_loaded_ranges[vid]:
                if r_end <= start or r_start >= end:
                    # 无重叠: 保留区间
                    new_ranges.append((r_start, r_end))
                else:
                    # 有重叠: 分割区间
                    if r_start < start:
                        new_ranges.append((r_start, start))
                    if r_end > end:
                        new_ranges.append((end, r_end))
            v_seg_loaded_ranges[vid] = new_ranges
            if not v_seg_loaded_ranges[vid]:
                if vid in loaded_v_seg_indices:
                    loaded_v_seg_indices.remove(vid)
        
        def emit_reload_virtual(time, vid, logical_end):
            """
            为虚拟段的缺失范围生成 Reload 操作
            
            该函数计算虚拟段的哪些部分尚未加载，
            并为这些范围生成 Reload 操作。
            
            参数:
                time (int): 重载操作的开始时间
                vid (int): 虚拟段 ID
                logical_end (int): 要加载到的目标逻辑结束偏移量
            
            副作用:
                - 更新 T_io（全局 I/O 时间线）
                - 更新 current_hbm_usage
                - 向输出缓冲区添加 Reload 操作
            """
            nonlocal T_io, current_hbm_usage
            
            # 计算缺失的范围
            current_ranges = v_seg_loaded_ranges[vid]
            missing = []
            
            if not current_ranges:
                # 没有加载任何内容: 重载整个范围
                missing = [(0, logical_end)]
            else:
                # 查找已加载范围中的空隙
                covered = 0
                for r_start, r_end in sorted(current_ranges):
                    if covered < r_start and covered < logical_end:
                        missing.append((covered, min(r_start, logical_end)))
                    covered = max(covered, r_end)
                if covered < logical_end:
                    missing.append((covered, logical_end))
            
            # 为缺失范围生成 Reload 操作
            op_time = time
            total_loaded = 0
            
            for l_start, l_end in missing:
                acc = 0
                for p_start, p_size in self.v_seg_sub_segments[vid]:
                    seg_log_end = acc + p_size
                    overlap_s = max(acc, l_start)
                    overlap_e = min(seg_log_end, l_end)
                    
                    if overlap_s < overlap_e:
                        load_len = overlap_e - overlap_s
                        phys = p_start + (overlap_s - acc)
                        out_buf.append(op_time, "Reload", phys, load_len)
                        op_time += 40 * load_len  # 每字节 40 周期
                        total_loaded += load_len
                    
                    acc += p_size
                    if acc >= l_end:
                        break
                
                add_loaded_range(vid, l_start, l_end)
            
            # 更新全局状态
            T_io = op_time
            current_hbm_usage += total_loaded
        
        def emit_offload_virtual(time, vid, amount):
            """
            使用 LIFO 策略为虚拟段生成 Offload 操作
            
            使用后进先出 (LIFO) 驱逐策略: 最近加载的范围
            优先被卸载。
            
            参数:
                time (int): 卸载操作的开始时间
                vid (int): 虚拟段 ID
                amount (int): 要卸载的字节数
            
            副作用:
                - 更新 T_io（全局 I/O 时间线）
                - 更新 current_hbm_usage
                - 向输出缓冲区添加 Offload 操作
            """
            nonlocal T_io, current_hbm_usage
            
            current_loaded = get_loaded_amount(vid)
            if current_loaded == 0:
                return
            
            offload_amt = min(amount, current_loaded)
            
            # LIFO 卸载策略: 从最后加载的范围开始
            ranges_to_offload = []
            acc_off = 0
            
            for r_start, r_end in sorted(v_seg_loaded_ranges[vid], reverse=True):
                if acc_off >= offload_amt:
                    break
                needed = offload_amt - acc_off
                if r_end - r_start <= needed:
                    # 卸载整个范围
                    ranges_to_offload.append((r_start, r_end))
                    acc_off += r_end - r_start
                else:
                    # 从末尾部分卸载
                    ranges_to_offload.append((r_end - needed, r_end))
                    acc_off += needed
            
            # 生成 Offload 操作
            op_time = time
            total_offloaded = 0
            
            for l_start, l_end in ranges_to_offload:
                acc = 0
                for p_start, p_size in self.v_seg_sub_segments[vid]:
                    seg_log_end = acc + p_size
                    overlap_s = max(acc, l_start)
                    overlap_e = min(seg_log_end, l_end)
                    
                    if overlap_s < overlap_e:
                        off_len = overlap_e - overlap_s
                        phys = p_start + (overlap_s - acc)
                        out_buf.append(op_time, "Offload", phys, off_len)
                        op_time += 40 * off_len
                        total_offloaded += off_len
                    
                    acc += p_size
                    if acc >= l_end:
                        break
                
                remove_loaded_range(vid, l_start, l_end)
            
            # 更新全局状态
            T_io = op_time
            current_hbm_usage -= total_offloaded
        
        def get_next_use(vid, g_idx):
            """
            获取下一个将访问此虚拟段的任务组索引
            
            使用缓存指针实现 O(1) 均摊查找。
            
            参数:
                vid (int): 虚拟段 ID
                g_idx (int): 当前任务组索引
            
            返回:
                int: 访问此段的下一个任务组索引，或 INFINITY_USE
            """
            ac_list = self.v_seg_access_groups[vid]
            ptr = v_seg_next_access_ptr[vid]
            
            # 将指针推进到当前任务组之后
            while ptr < len(ac_list) and ac_list[ptr] <= g_idx:
                ptr += 1
            
            v_seg_next_access_ptr[vid] = ptr  # 缓存供下次查找使用
            return ac_list[ptr] if ptr < len(ac_list) else INFINITY_USE
        
        def find_best_victim(needed, protect_set, cur_g_idx, io_limit=None):
            """
            使用基于距离的评分查找最佳驱逐虚拟段
            
            评分策略:
                1. 垃圾（无未来使用）: 最高优先级
                2. 求解器候选（单次驱逐解决赤字）: 高优先级
                3. 贪心候选（部分驱逐）: 较低优先级
            
            评分公式: distance_to_next_use / sqrt(segment_size)
                - 偏好远期使用的段
                - 惩罚大段（避免重新加载开销）
            
            参数:
                needed (int): 即将操作需要的字节数
                protect_set (set): 不能被驱逐的段 ID 集合
                cur_g_idx (int): 当前任务组索引
                io_limit (int, optional): 候选的最大解锁时间
            
            返回:
                tuple: (victim_id, amount_to_offload) 或 (-1, 0) 如果未找到受害者
            """
            deficit = (current_hbm_usage + needed) - self.M
            if deficit <= 0:
                return (-1, 0)
            
            # 对候选进行分类
            inf_cands = []      # 垃圾（无未来使用）
            solver_cands = []   # 可以一次驱逐解决赤字
            all_cands = []      # 所有有效候选
            
            for vid in loaded_v_seg_indices:
                if vid in protect_set:
                    continue
                if io_limit and v_seg_unlock_time[vid] > io_limit:
                    continue
                
                nu = get_next_use(vid, cur_g_idx)
                ut = v_seg_unlock_time[vid]
                
                if nu == INFINITY_USE:
                    # 垃圾: 不会再被使用
                    inf_cands.append(((1, 0, -ut), vid))
                else:
                    # 计算优先级分数
                    dist = nu - cur_g_idx
                    score_val = dist * self.inv_sqrt_sizes[vid]
                    wait = max(0, ut - T_io)
                    final_score = score_val - (wait * 0.5)  # 惩罚被锁定的段
                    
                    all_cands.append(((0, final_score, -ut), vid))
                    
                    # 检查该段是否可以单独解决赤字
                    if get_loaded_amount(vid) >= deficit:
                        solver_cands.append(((0, final_score, -ut), vid))
            
            # 优先级 1: 首先驱逐垃圾段
            if inf_cands:
                inf_cands.sort(key=lambda x: x[0], reverse=True)
                vid = inf_cands[0][1]
                return (vid, get_loaded_amount(vid))  # 完全驱逐
            
            # 优先级 2: 优先使用求解器候选（一次性解决方案）
            best_solver = max(solver_cands, key=lambda x: x[0]) if solver_cands else None
            best_greedy = max(all_cands, key=lambda x: x[0]) if all_cands else None
            
            if best_solver:
                # 使用求解器，除非贪心明显更好
                if not best_greedy or best_solver[0][1] * 1.1 > best_greedy[0][1]:
                    amt = get_loaded_amount(best_solver[1])
                    return (best_solver[1], min(amt, deficit))
            
            # 优先级 3: 使用贪心候选（部分驱逐）
            if best_greedy:
                amt = get_loaded_amount(best_greedy[1])
                return (best_greedy[1], min(amt, deficit))
            
            # 未找到有效的受害者
            return (-1, 0)
        
        # ==========================================
        # 阶段 7: 主调度循环 (Main Scheduling Loop)
        # ==========================================
        for g_idx in range(num_groups):
            start_time, duration, req_ids = self.group_info[g_idx]
            needed = self.group_needed_vsegs[g_idx]
            T_npu_ready = last_group_compute_end
            
            # --------------------------------------------
            # 步骤 A: 识别所需的加载 (Identify Required Loads)
            # --------------------------------------------
            to_load = []
            need_bytes = 0
            
            for vid in needed:
                rem = self.v_seg_total_size[vid] - get_loaded_amount(vid)
                if rem > 0:
                    to_load.append(vid)
                    need_bytes += rem
            
            # --------------------------------------------
            # 步骤 B: 驱逐以腾出空间 (Evict to Make Space)
            # --------------------------------------------
            while current_hbm_usage + need_bytes > self.M:
                vid, amt = find_best_victim(need_bytes, set(needed), g_idx)
                if vid != -1:
                    t_start = max(T_io, v_seg_unlock_time[vid])
                    emit_offload_virtual(t_start, vid, amt)
                else:
                    # 无法腾出足够空间: 退出并尽力而为
                    break
            
            # --------------------------------------------  
            # 步骤 C: 执行加载 (Execute Loads)
            # --------------------------------------------
            if to_load:
                # 按物理地址排序以减少寻道时间
                to_load.sort(key=lambda v: self.v_seg_sub_segments[v][0][0])
                
                for vid in to_load:
                    rem = self.v_seg_total_size[vid] - get_loaded_amount(vid)
                    if rem > 0:
                        emit_reload_virtual(T_io, vid, self.v_seg_total_size[vid])
            
            # --------------------------------------------
            # 步骤 D: 执行 Visit
            # --------------------------------------------
            T_data_ready = T_io
            T_visit_start = max(T_npu_ready, start_time, T_data_ready)
            T_group_end = T_visit_start + duration
            est_group_start_time[g_idx] = T_visit_start
            
            # 生成 Visit 操作
            for rid in req_ids:
                out_buf.append(T_visit_start, "Visit", rid, 0)
            
            # 锁定所有需要的段直到 NPU 完成
            for vid in needed:
                v_seg_unlock_time[vid] = max(v_seg_unlock_time[vid], T_group_end)
            
            # --------------------------------------------
            # 步骤 E: 预取未来数据（如果时间允许）
            # --------------------------------------------
            if g_idx < num_groups - 1 and T_io < T_group_end:
                # 查找第一个数据不完整的任务组（屏障）
                first_missing = -1
                lookahead = min(num_groups, g_idx + self.LOOKAHEAD_DEPTH)
                
                for pg in range(g_idx+1, lookahead):
                    pg_need = self.group_needed_vsegs[pg]
                    ok = True
                    for v in pg_need:
                        if get_loaded_amount(v) < self.v_seg_total_size[v]:
                            ok = False
                            break
                    if not ok:
                        first_missing = pg
                        break
                
                if first_missing == -1:
                    first_missing = lookahead + 1
                
                # 构建带松弛分数的预取候选
                cands = []
                debt = 0  # 累积的先前任务组 I/O 债务
                
                for pg in range(g_idx+1, lookahead):
                    pg_need = self.group_needed_vsegs[pg]
                    deadline = max(est_group_start_time[pg], T_group_end)
                    den = group_density_factor[pg]
                    grp_unloaded = 0
                    
                    for v in pg_need:
                        rem = self.v_seg_total_size[v] - get_loaded_amount(v)
                        if rem > 0:
                            cost = 40 * rem
                            slack = (deadline - (T_io + cost + debt * 40)) / den
                            distance = pg - g_idx  # 到下次使用的距离
                            cands.append((slack, distance, v, rem, pg))
                            grp_unloaded += rem
                    
                    debt += grp_unloaded
                
                # 排序候选: Late（紧急）优先，然后 Early (SJF)
                late, early = [], []
                for c in cands:
                    if c[0] < 0:  # 负松弛: 紧急
                        late.append(c)
                    else:
                        early.append(c)
                
                late.sort(key=lambda x: x[4])              # 按任务组 FCFS
                early.sort(key=lambda x: (x[0], x[1]))     # SJF 带距离平局
                cands = late + early
                
                # 执行预取
                for slack, distance, vid, rem, pg in cands:
                    t_left = T_group_end - T_io
                    if t_left <= 0:
                        break
                    
                    real_rem = self.v_seg_total_size[vid] - get_loaded_amount(vid)
                    if real_rem <= 0:
                        continue
                    
                    max_load = t_left // 40
                    if max_load <= 0:
                        break
                    
                    amt = min(real_rem, max_load)
                    
                    # 保护: 如果内存紧张，不要预取屏障之后的数据
                    if pg > first_missing and current_hbm_usage + amt >= self.M:
                        continue
                    
                    # 如果需要，尝试与一个次要的段交换
                    if current_hbm_usage + amt > self.M:
                        deficit = (current_hbm_usage + amt) - self.M
                        best_s = -1
                        best_score = -float('inf')
                        
                        # 查找交换受害者（垃圾或远期段）
                        for cv in loaded_v_seg_indices:
                            if cv == vid:
                                continue
                            if v_seg_unlock_time[cv] > T_io:
                                continue
                            
                            nu = get_next_use(cv, g_idx)
                            if nu <= pg:  # 不要交换目标之前需要的段
                                continue
                            
                            if nu == INFINITY_USE:
                                # 找到垃圾: 立即使用
                                best_s = cv
                                break
                            
                            # 根据距离和大小评分
                            sc = (nu - pg) * self.inv_sqrt_sizes[cv]
                            if get_loaded_amount(cv) >= deficit and sc > best_score:
                                best_score = sc
                                best_s = cv
                        
                        # 如果有利可图，执行交换
                        if best_s != -1:
                            swap_amt = min(get_loaded_amount(best_s), deficit)
                            off_cost = 40 * swap_amt
                            
                            if T_io + off_cost + 40 <= T_group_end:
                                emit_offload_virtual(T_io, best_s, swap_amt)
                                new_max = (T_group_end - T_io) // 40
                                amt = min(real_rem, new_max)
                            else:
                                amt = 0  # 交换时间不足
                        else:
                            amt = 0  # 没有合适的受害者
                    
                    # 执行预取
                    if amt > 0 and current_hbm_usage + amt <= self.M:
                        emit_reload_virtual(T_io, vid, get_loaded_amount(vid) + amt)
            
            # 更新 NPU 时间线
            last_group_compute_end = T_group_end
        
        # ==========================================
        # 阶段 8: 输出结果 (Output Results)
        # ==========================================
        ops = out_buf.flush()
        sys.stdout.write('\n'.join(ops))
        sys.stdout.write(f"\nFin {max(last_group_compute_end, T_io)}\n")


# ==========================================
# 策略选择器 (Strategy Selector)
# ==========================================

class Selector:
    """
    智能策略选择器 - 基于工作负载特征自动选择最优调度策略
    
    分析三大关键指标：
        1. max_p (内存压力): HBM 峰值利用率
        2. io_density (IO密度): 带宽需求强度 (字节/时间)
        3. avg_seg_size (平均段大小): 内存粒度
    
    选择逻辑：
        - 高内存压力 (≥0.95) → 保守策略，避免颠簸
        - 高IO密度 (>1.05) → 激进合并 + 深度预取
        - 大段场景 (M * 0.125) → 合并策略，提升IO效率
        - 默认 → 平衡策略
    """
    
    def __init__(self):
        """从标准输入读取并分词"""
        self.input_data = sys.stdin.read().split()
    
    @staticmethod
    def adjust_lookahead(base_lookahead, num_groups, max_p, io_density):
        """
        综合考虑任务组数量、内存压力和IO密度动态调整预取深度
        
        多维度调整策略：
        1. 基于任务组数量确定基础比例
        2. 根据内存压力调整（高压→保守，宽裕→激进）
        3. 根据IO密度调整（密集→激进，宽裕→保守）
        
        参数:
            base_lookahead (int): 策略指定的基础预取深度
            num_groups (int): 任务组总数
            max_p (float): 内存压力（0-1，峰值利用率）
            io_density (float): IO密度（相对于基线0.025）
        
        返回:
            int: 调整后的预取深度
        """
        # 步骤1: 基于任务组数量的基础比例
        if num_groups <= 40:
            # 极小规模：基础比例20%
            base_ratio = 0.20
            min_val = 8
        elif num_groups <= 100:
            # 小规模：基础比例30%
            base_ratio = 0.30
            min_val = 10
        elif num_groups <= 300:
            # 中规模：基础比例50%
            base_ratio = 0.50
            min_val = 15
        else:
            # 大规模：使用完整基础值，不再缩放
            return min(base_lookahead, num_groups - 1)
        
        # 步骤2: 根据内存压力调整
        if max_p >= 0.95:
            # 内存高压：更保守（减少20%）
            pressure_factor = 0.8
        elif max_p >= 0.85:
            # 中等压力：略微保守（减少10%）
            pressure_factor = 0.9
        else:
            # 内存宽裕：保持原比例
            pressure_factor = 1.0
        
        # 步骤3: 根据IO密度调整
        if io_density > 1.2:
            # IO密集：更激进（增加30%）
            io_factor = 1.3
        elif io_density > 1.05:
            # 中等IO：略微激进（增加15%）
            io_factor = 1.15
        else:
            # IO宽裕：保持原比例
            io_factor = 1.0
        
        # 综合调整：基础比例 × 内存因子 × IO因子
        final_ratio = base_ratio * pressure_factor * io_factor
        scaled = int(num_groups * final_ratio)
        
        # 确保在合理范围内
        return min(base_lookahead, max(min_val, scaled))
    
    def analyze_and_run(self):
        """
        分析工作负载特征并运行最优规划器
        
        流程：
        1. 解析输入，提取工作负载特征
        2. 计算三大关键指标
        3. 基于指标阈值选择最优策略
        4. 实例化并运行选定的规划器
        """
        if not self.input_data:
            return
        
        # ==========================================
        # 步骤 1: 解析输入数据
        # ==========================================
        iterator = iter(self.input_data)
        try:
            L = int(next(iterator))  # 地址空间大小
            M = int(next(iterator))  # HBM 容量
            N = int(next(iterator))  # 请求数量
            
            requests = []
            for i in range(N):
                requests.append((
                    int(next(iterator)),  # 地址
                    int(next(iterator)),  # 大小
                    int(next(iterator)),  # 开始时间
                    int(next(iterator)),  # 持续时间
                    i                      # 请求 ID
                ))
        except StopIteration:
            return
        
        # ==========================================
        # 步骤 2: 特征提取 - 平均段大小
        # ==========================================
        # 对地址空间进行离散化，计算物理段数量
        points = {0, L}
        for r in requests:
            points.add(r[0])
            points.add(r[0] + r[1])
        
        sorted_points = sorted(list(points))
        temp_cnt = 0
        for i in range(len(sorted_points) - 1):
            if sorted_points[i+1] > sorted_points[i]:
                temp_cnt += 1
        
        avg_seg_size = L / temp_cnt if temp_cnt else 0
        
        # ==========================================
        # 步骤 3: 特征提取 - 内存压力与 IO 密度
        # ==========================================
        # 按开始时间分组请求
        groups = {}
        for r in requests:
            if r[2] not in groups:
                groups[r[2]] = []
            groups[r[2]].append(r)
        
        sorted_times = sorted(groups.keys())
        
        # 内存压力：各时间片的峰值内存占用率
        max_p = 0
        
        # IO 密度分析：使用滑动窗口检测局部 IO 峰值
        window_size = 10  # 窗口大小（任务组数量）
        window_io_bytes = []
        window_compute_time = []
        
        max_window_io_density = 0.0
        total_io_all = 0
        total_dur_all = 0
        
        for i, t in enumerate(sorted_times):
            reqs = groups[t]
            dur = reqs[0][3]
            mem = sum(r[1] for r in reqs)
            
            # 更新峰值内存压力
            max_p = max(max_p, mem / M)
            
            # 累积窗口数据（IO 成本 = 数据量 × 40 周期/字节）
            curr_io = mem * 40
            window_io_bytes.append(curr_io)
            window_compute_time.append(dur)
            
            total_io_all += curr_io
            total_dur_all += dur
            
            # 维护固定窗口大小
            if len(window_io_bytes) > window_size:
                window_io_bytes.pop(0)
                window_compute_time.pop(0)
            
            # 计算窗口内的 IO 密度
            win_io_sum = sum(window_io_bytes)
            win_dur_sum = sum(window_compute_time)
            
            if win_dur_sum > 0:
                local_density = win_io_sum / win_dur_sum
                max_window_io_density = max(max_window_io_density, local_density)
        
        # 全局平均 IO 密度
        avg_io_density = total_io_all / total_dur_all if total_dur_all > 0 else 0
        
        # ==========================================
        # 步骤 4: 策略决策
        # ==========================================
        
        # 计算任务组总数（用于动态调整预取深度）
        num_groups = len(sorted_times)
        
        # 计算实际使用的IO密度（取窗口峰值和全局平均的较大值）
        actual_io_density = max(max_window_io_density, avg_io_density) / 0.025
        
        # 优先级 1: 内存高压 - 生存第一
        if max_p >= 0.95:
            # 关闭合并，使用保守的预取深度，避免内存颠簸
            base_lookahead = 100
            lookahead = self.adjust_lookahead(base_lookahead, num_groups, max_p, actual_io_density)
            solver = UniversalPlanner(self.input_data, enable_merge=False, lookahead=lookahead)
        
        # 优先级 2: IO 瓶颈 - 带宽优先
        elif max_window_io_density > 1.2 or avg_io_density > 1.05:
            # 开启合并 + 深度预取，最大化带宽利用
            # UniversalPlanner 会根据每个任务组的密度因子自动调整
            base_lookahead = 200
            lookahead = self.adjust_lookahead(base_lookahead, num_groups, max_p, actual_io_density)
            solver = UniversalPlanner(self.input_data, enable_merge=True, lookahead=lookahead)
        
        # 优先级 3: 大段场景 - IO 效率优先
        # 使用相对于内存大小的阈值（M 的 12.5%）而非固定值
        elif avg_seg_size > M * 0.125:
            # 大段数据适合合并加载，使用中等预取深度
            base_lookahead = 100
            lookahead = self.adjust_lookahead(base_lookahead, num_groups, max_p, actual_io_density)
            solver = UniversalPlanner(self.input_data, enable_merge=True, lookahead=lookahead)
        
        # 优先级 4: 默认平衡策略
        else:
            # 适用于通用场景，平衡内存与 IO
            base_lookahead = 50
            lookahead = self.adjust_lookahead(base_lookahead, num_groups, max_p, actual_io_density)
            solver = UniversalPlanner(self.input_data, enable_merge=True, lookahead=lookahead)
        
        # 执行选定的策略
        solver.run()


# ==========================================
# 程序入口 (Entry Point)
# ==========================================

if __name__ == "__main__":
    Selector().analyze_and_run()
